原题链接:POJ 3683
题目大意:有对人结婚仪式,对第场结婚仪式开始或结束时需要进行一个时长为的特殊仪式,起始时间是,结束时间是则要么选,要么选这两个时间段之一.问每场婚礼是否都至少有一个特殊仪式.如果有,则额外输出具体方案.
注意:牧师Jhon虽然不能同时出现在两个婚礼,但是他在两个婚礼之间赶路的时间可以忽略.
数据范围:
题目的时间以的格式给出
样例输入:
2
08:00 09:00 30
08:15 09:00 20
样例输出
YES
08:00 08:30
08:40 09:00
这题乍看上去,可能是一个关于时间的贪心.但是这题每个人的选择都是有两种的,所以不大好做,形式上比较接近问题.把看成是第场婚礼去了开头,看成是去了结尾.考虑如何建图:先以的方式遍历每场婚礼,两场婚礼分别为和,若和()时间段上有冲突,就说明两场婚礼肯定不能同时去做特殊仪式,在图上对和连边,和和$i + (1 - p)*N)连边.
具体来说,我们先划分成四种情况,与两边是否是第一段开头有关:
①00
即两个开头的时间冲突了,判据是起始时间是否覆盖比开头高就行了
if(min(S{i] + D[i],S[j] + D{j]) > max(S{i],S[j]))
add(i,j + n), add(j,i + n)
②01
即前者的开头和后者的结尾段冲突了,判断两者是否相交上了
if(min(S[i] + D[i],T[j]) > max(S[i],T[j] - D[j]))
add(i,j),add(j + n,i + n);
当然你也可以写成一个区间判断覆盖的形式,不过我这里直接用白书的写法来解决这个问题了,比那个区间覆盖的方式稍微好写一点,如下:
bool collision(int a, int b, int c, int d) {
if (a >= c && a < d || b > c && b <= d || a <= c && b >= d) return 1;
return 0;
}
另外两种就不特别说明了
之后判断是否有解,如果有解的话,在之后的新图里,如果拓扑排序的位置中,的位置早于,则把设置成假,另外一个设置成真.最后输出即可
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005,M = 4e6+7;
int edge[M],succ[M],ver[N],idx;
int time_stamp,dfn[N],low[N];
int n,m;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,siz[N];
int din[N],dout[N];
int S[N],T[N],D[N],opid[N],res[N];
void add(int u,int v)
{
edge[idx] = v;
succ[idx] = ver[u];
ver[u] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++time_stamp;
stk[++top] = u,in_stk[u] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int j = edge[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(in_stk[j])
low[u] = min(low[u],dfn[j]);
}
if(dfn[u] == low[u])
{
int y;
++scc_cnt;
do
{
y = stk[top--];
in_stk[y] = 0;
id[y] = scc_cnt;
siz[scc_cnt]++;
}while(y != u);
}
}
int main()
{
memset(ver,-1,sizeof ver);
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
int h1,m1,h2,m2;int d;
scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&d);
S[i] = h1 * 60 + m1;
T[i] = h2 * 60 + m2;
D[i] = d;
}
for(int i = 1;i <= n;++i)
for(int j = 1;j < i;++j)
{
//00
if(min(S[i] + D[i],S[j] + D[j]) > max(S[i],S[j]))
{
add(i,j + n);
add(j,i + n);
}
//01
if(min(S[i] + D[i],T[j]) > max(S[i],T[j] - D[j]))
{
add(i,j);
add(j + n,i + n);
}
//10
if(min(T[i],S[j] + D[j]) > max(T[i] - D[i],S[j]))
{
add(i + n,j + n);
add(j,i);
}
//11
if(min(T[i],T[j]) > max(T[i] - D[i],T[j] - D[j]))
{
add(i + n,j);
add(j + n,i);
}
}
for(int i = 1;i <= 2 * n;++i)
if(!dfn[i])
tarjan(i);
reverse(stk + 1,stk + 1 + 2 * n);
int ok = 1;
for(int i = 1;i <= n;++i)
{
if(id[i] == id[i + n])
{
ok = 0;
break;
}
}
if(!ok) puts("NO");
else
{
puts("YES");
for(int i = 1;i <= n;++i)
{
if(id[i] > id[i + n])
printf("%02d:%02d %02d:%02d\n",(T[i] - D[i]) / 60,(T[i] - D[i]) % 60,T[i] / 60,T[i] % 60);
else
printf("%02d:%02d %02d:%02d\n",S[i] / 60,S[i] % 60,(S[i] + D[i]) / 60,(S[i] + D[i]) % 60);
}
}
return 0;
}